package org.example;

import org.junit.Test;


public class AppTest02
{

    // 加一1
    @Test
    public void plusOne01(int[] digits)
    {
        class Solution {
            public int[] plusOne(int[] digits) {
                int len = digits.length;
                for (int i = len - 1; i >= 0 ; i--) {
                    digits[i]++;
                    digits[i] %= 10;
                    if (digits[i] != 0){
                        return digits;
                    }
                }
                digits = new int[len + 1];
                digits[0] = 1;
                return digits;
            }
        }
    }
    // 加一2
    @Test
    public void plusOne02(int[] digits)
    {
        class Solution {
            public int[] plusOne(int[] digits) {
                for (int i = digits.length - 1; i >= 0; i--) {
                    digits[i] = (digits[i] + 1) % 10;
                    if (digits[i] != 0) {
                        return digits;
                    }
                }
                //todo 复用digits，前面不加类型
                digits = new int[digits.length + 1];
                digits[0] = 1;
                return digits;
            }
        }
    }
    // 加一3
    @Test
    public void plusOne03(int[] digits)
    {
        class Solution {
            public int[] plusOne(int[] digits) {
                for (int i = digits.length - 1; i >= 0 ; i--) {
                    digits[i] = (digits[i] + 1) % 10;
                    if (digits[i] != 0) {
                        return digits;
                    }
                }
                digits = new int[digits.length + 1];
                digits[0] = 1;
                return digits;
            }
        }
    }

    //x的平方根1
    @Test
    public void mySqrt01() {
        class Solution {
            public int mySqrt (int x) {
                int left = 0, right = x, ans = -1;
                while (left <= right) {
                    int mid = (right - left) / 2 + left;
                    //todo 注意数据类型
                    if ((long)mid * mid <= x) {
                        ans = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                return ans;
            }
        }
    }
    //x的平方根2
    @Test
    public void mySqrt02() {
        class Solution {
            public int mySqrt (int x) {
                int left = 0, right = x, ans = -1;
                while (left <= right) {
                    int mid = (right - left) / 2 + left;
                    if ((long) mid * mid <= x) {
                        ans = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                return ans;
            }
        }
    }
    //x的平方根3
    @Test
    public void mySqrt03() {
        class Solution {
            public int mySqrt (int x) {
                int left = 0, right = x, ans = -1;
                while (left <= right) {
                    int mid = (right - left) / 2 + left;
                    if (mid * mid <= x) {
                        ans = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                return ans;
            }
        }
    }

    //爬楼梯1
    @Test
    public void climbStairs01 () {
        class Solution {
            public int climbStairs(int n) {
                int p = 0, q = 0, r = 1;
                for (int i = 0; i < n ; i++) {
                    p = q;
                    q = r;
                    r = p + q;
                }
                return r;
            }
        }
    }
    //爬楼梯2
    @Test
    public void climbStairs02 () {
        class Solution {
            public int climbStairs(int n) {
                int p = 0, q = 0, r = 1;
                for (int i = 0; i < n; i++) {
                    p = q;
                    q = r;
                    r = p + q;
                }
                return r;
            }
        }
    }
    //爬楼梯3
    class Solution {
        public int climbStairs(int n) {
            int p = 0, q = 0, r = 1;
            for (int i = 0; i < n; i++) {
                p = q;
                q = r;
                r = p + q;
            }
            return r;
        }
    }

    //删除排序链表中的重复元素1
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode current = head;
            while (current != null && current.next != null) {
                if (current.next.val == current.val) {
                    current.next = current.next.next;
                } else {
                    current = current.next;
                }
            }
            return head;
        }
    }
    //删除排序链表中的重复元素2
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode current = head;
            while (current != null && current.next != null) {
                if (current.val == current.next.val) {
                    current.next = current.next.next;
                //todo 要加else
                } else {
                    current = current.next;
                }
            }
            return head;
        }
    }
    //删除排序链表中的重复元素3
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            ListNode current = head;
            while (current != null && current.next != null) {
                if (current.val == current.next.val) {
                    current.next = current.next.next;
                } else {
                    current = current.next;
                }
            }
            return head;
        }
    }

    //合并两个有序数组1
    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int p1 = m - 1;
            int p2 = n - 1;
            int p = n + m - 1;
            while (p1 >= 0 && p2 >= 0) {
                nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
            }
            System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
        }
    }
    //合并两个有序数组2
    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int p1 = m - 1, p2 = n - 1, p = m + n - 1;
            while (p1 >= 0 && p2 >= 0) {
                nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
            }
            if (p1 == -1) {
                System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
            }
        }
    }
    //合并两个有序数组3
    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int p1 = m - 1, p2 = n - 1, p = m + n - 1;
            while (p1 >= 0 && p2 >= 0) {
                nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
            }
            System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
        }
    }

    //相同的树1
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) return true;
            else if (p == null || q == null) return false;
            else if (p.val != q.val) return false;
            else return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
    //相同的树2
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) return true;
            else if (p == null || q == null) return false;
            else if (p.val != q.val) return false;
            else {
                return  isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
        }
    }
    //相同的树3
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if ( p == null && q == null) return true;
            else if (p == null || q == null) return false;
            else return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

    //对称二叉树1
    class Solution {

        public boolean isSymmetric(TreeNode root) {
            // todo 记得return关键字
            return check(root, root);
        }

        public boolean check(TreeNode p, TreeNode q) {
            if (p == null && q == null) return true;
            else if (p == null || q == null) return false;
            else if (p.val != q.val) return false;
            else return check(p.left, q.right) && check(p.right, q.left);
        }

    }
    //对称二叉树2
    class Solution {

        public boolean isSymmetric(TreeNode root) {
            return check(root, root)
        }

        public boolean check(TreeNode t1, TreeNode t2) {
            if (t1 == null && t2 == null) return true;
            else if (t1 == null || t2 == null) return false;
            else return (t1.val == t2.val) && check(t1.left, t2.right) && check(t1.right, t2.left);
        }

    }
    //对称二叉树3
    class Solution {

        public boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }

        public boolean check(TreeNode t1, TreeNode t2) {
            if (t1 == null && t2 == null) return true;
            else if (t1 == null || t2 == null) return false;
            else return t1.val == t2.val && check(t1.left, t2.right) && check(t1.right, t2.left);
        }

    }

    //二叉树的最大深度1
    class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) return 0;
            else {
                int leftHeight = maxDepth(root.left);
                int rightHeight = maxDepth(root.right);
                return Math.max(leftHeight, rightHeight) + 1;
            }
        }
    }
    //二叉树的最大深度2
    class Solution {
        public int maxDepth(TreeNode root) {
           if (root == null) return 0;
           return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
    //二叉树的最大深度3
    class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }

    //有序数组转换为二叉搜索树1
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return helper(nums, 0, nums.length -1);
        }

        private TreeNode helper(int[] nums, int left, int right) {
            if (left > right){
                return null;
            }
            int mid = (left + right) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = helper(nums, left, mid -1);
            root.right = helper(nums, mid + 1, right);
            return root;
        }
    }
    //有序数组转换为二叉搜索树2
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return helper(nums, 0, nums.length - 1);
        }

        private TreeNode helper (int[] nums, int left, int right) {
            // todo 递归结束条件写在前面，返回的是null
            if (left > right) return null;
            int mid = (left + right) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = helper(nums, left, mid - 1);
            root.right = helper(nums, mid + 1, right);
            return root;
        }

    }
    //有序数组转换为二叉搜索树3
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return helper(nums, 0, nums.length - 1);
        }

        private TreeNode helper (int[] nums, int left, int right) {
            if (left > right) return null;
            int mid = (left + right) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = helper(nums, left, mid - 1);
            root.right = helper(nums, mid + 1, right);
            return root;
        }
    }

    //平衡二叉树1
    class Solution {
        public boolean isBalanced(TreeNode root){
            if (root == null) return true;
            return Math.abs(height(root.left) - height(root.right)) <= 1 && 
                    isBalanced(root.left) && isBalanced(root.right);
        }
        private int height(TreeNode root) {
            if (root == null) return 0;
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
    //平衡二叉树2
    class Solution {
        public boolean isBalanced(TreeNode root){
            if (root == null) return true;
            return Math.abs(height(root.left) - height(root.right)) <= 1 &&
                    isBalanced(root.left) && isBalanced(root.right);
        }

        private int height(TreeNode root) {
            if (root == null) return 0;
            return Math.max(height(root.left), height(root.right)) + 1;
        }

    }
    //平衡二叉树3
    class Solution {
        public boolean isBalanced(TreeNode root){
            if (root == null) return true;
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }

        private int height(TreeNode root) {
            if (root == null) return 0;
            return Math.max(height(root.left), height(root.right)) + 1;
        }

    }

    //二叉树的最小深度1
    class Solution {
        public int minDepth(TreeNode root) {
            if (root == null) return 0;
            if (root.left == null && root.right == null) return 1;
            int min_depth = Integer.MAX_VALUE;
            if (root.left != null) min_depth = minDepth(root.left);
            if (root.right != null) min_depth = Math.min(minDepth(root.right), min_depth);
            return min_depth + 1;
        }
    }
    //二叉树的最小深度2
    class Solution {
        public int minDepth(TreeNode root) {
            if (root == null) return 0;
            if (root.left == null && root.right == null) return 1;
            int res = Integer.MAX_VALUE;
            if (root.left != null) res = minDepth(root.left);
            if (root.right != null) res = Math.min(res, minDepth(root.right));
            return res + 1;
        }
    }
    //二叉树的最小深度3
    class Solution {
        public int minDepth(TreeNode root) {
            if (root == null) return 0;
            if (root.left == null && root.right == null) return 1;
            int res = Integer.MAX_VALUE;
            if (root.left != null) res = Math.min(res, minDepth(root.left));
            if (root.right != null ) res = Math.min(res,minDepth(root.right));
            return res + 1;
        }
    }
}































